import numpy as np
import matplotlib.pyplot as plt
import cv2 as cv


class XET:
    x = 0
    dx = 0
    yMax = 0

    def __lt__(self, other):
        return int(self.x) < int(other.x)

    def __repr__(self):
        return str(self.x) + " " + str(self.dx) + " " + str(self.yMax)


def PolyScan(points, img):
    pointsCount = len(points)
    maxy = 0
    for i in points:
        if i[1] > maxy:
            maxy = i[1]

    pAET = []
    pNET = list(np.ones(1024))
    for i in range(1024):
        pNET[i] = []

    i = 0
    # 构造新边表
    while i <= maxy:
        for j in range(pointsCount):
            if points[j][1] == i:
                if points[(j - 1 + pointsCount) % pointsCount][1] > points[j][1]:
                    p = XET()
                    p.x = points[j][0]
                    p.yMax = points[(j - 1 + pointsCount) % pointsCount][1]
                    p.dx = (points[(j - 1 + pointsCount) % pointsCount][0] - points[j][0]) / (
                            points[(j - 1 + pointsCount) % pointsCount][1] - points[j][1])
                    pNET[i].append(p)

                if points[(j + 1 + pointsCount) % pointsCount][1] > points[j][1]:
                    p = XET()
                    p.x = points[j][0]
                    p.yMax = points[(j + 1 + pointsCount) % pointsCount][1]
                    p.dx = (points[(j + 1 + pointsCount) % pointsCount][0] - points[j][0]) / (
                            points[(j + 1 + pointsCount) % pointsCount][1] - points[j][1])
                    pNET[i].append(p)
        i = i + 1
    # 至此新边表构造完成
    for i in range(maxy + 1):
        # 删去活性边表中已经到yMax的结点，同时更新x坐标

        anotherList = []
        for j in pAET:
            if j.yMax != i:
                j.x = j.x + j.dx
                anotherList.append(j)
        pAET = anotherList
        # 在活性边表中加入新节点
        for j in pNET[i]:
            pAET.append(j)
        pAET.sort()
        # 利用活性边表画出扫描线
        for k in range(int(len(pAET) / 2)):
            start = pAET[2 * k].x
            end = pAET[2 * k + 1].x
            while start <= end:
                img[int(i)][int(start)] = 255
                start = start + 1


# points = [(20, 20), (50, 10), (110, 30), (110, 80), (50, 50), (20, 70)]
points = [(250, 450), (132, 88), (440, 312), (60, 312), (368, 88)]
img = np.zeros((500, 500), dtype=np.uint8)
PolyScan(points, img)

cv.imshow("a", img)
cv.waitKey(0)
